package HojaTrabajo3;

/**
 * MergeSort.java
 * @author Douglas Dávila
 * Ordenamiento por algoritmo de union 
 */


//tomado de http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html
public class MergeSort {
	/**el arreglo a ordenar*/
	private Comparable[] numbers;
	/**el arreglo intermediario para el ordenamiento*/
	private Comparable[] helper;
       /**
        * tomado de http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html
        * modificado el nombre de sort por mergeSort para conveniencia al llamar el metodo
        * @param list el arreglo a ordenar
        */
	public void mergesort(@SuppressWarnings("rawtypes") Comparable[] list) {
		this.numbers = list;
		int number = list.length;
		this.helper = new Comparable[number];
		sort(0, number - 1);
	}
        
        /**
         * tomado de http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html
         * modificado el nombre del metodo por sort para convenicia de semantica
         * @param low
         * @param high 
         */
	private void sort(int low, int high) {
		// Check if low is smaller then high, if not then the array is sorted
		if (low < high) {
			// Get the index of the element which is in the middle
			int middle = (low + high) / 2;
			// Sort the left side of the array
			sort(low, middle);
			// Sort the right side of the array
			sort(middle + 1, high);
			// Combine them both
			merge(low, middle, high);
		}
	}
        /**
         * tomado de http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html
         * @param low
         * @param middle
         * @param high 
         */
	private void merge(int low, int middle, int high) {

		// Copy both parts into the helper array
		for (int i = low; i <= high; i++) {
			helper[i] = numbers[i];
		}

		int i = low;
		int j = middle + 1;
		int k = low;
		// Copy the smallest values from either the left or the right side back
		// to the original array
		while (i <= middle && j <= high) {
			if ((Integer)helper[i] <= (Integer)helper[j]) {
				numbers[k] = helper[i];
				i++;
			} else {
				numbers[k] = helper[j];
				j++;
			}
			k++;
		}
		// Copy the rest of the left side of the array into the target array
		while (i <= middle) {
			numbers[k] = helper[i];
			k++;
			i++;
		}

	}
}